/**
 * 合并k个升序链表
 *
 * 给你一个链表数组，每个链表都已经按升序排列。
 * 请你将所有链表合并到一个升序链表中，返回合并后的链表。
 *
 * 示例 1：
 * 输入：lists = [[1,4,5],[1,3,4],[2,6]]
 * 输出：[1,1,2,3,4,4,5,6]
 * 解释：链表数组如下：
 * [
 *   1->4->5,
 *   1->3->4,
 *   2->6
 * ]
 * 将它们合并到一个有序链表中得到。
 * 1->1->2->3->4->4->5->6
 *
 * 示例 2：
 * 输入：lists = []
 * 输出：[]
 *
 * 示例 3：
 * 输入：lists = [[]]
 * 输出：[]
 */

import java.util.PriorityQueue;

/**
 * 1. 两个两个链表的合并, 因为每次合并两个链表的步骤基本一样, 所以我们应该可以用递归来写
 * 怎么用递归来写呢? 首先我们要做的就是如何将这些 list两两分开, 然后进行比较, 我首先想到的就是
 * 用循环让他们两两个进行比较, 这应该也是正常人的第一想法, 比较完之后再返回一个新的已经拍好序的 list
 * 这样就是原本的要排序的 list减少了一个, 但这个新生成的链表还要继续和后面的链表比较, 那不妨我们
 * 先自己建一个新链表, 然后再一个一个比较, 但是这个方法还是太笨了, 因为这个就是普通的暴力了
 * 我们想想之前是怎么对一个数组排序的呢, 有快排, 归并, 堆....
 * 假如我们将 lists 分成一个一个 list, 在排序, 最后合并, 这是不是和归并的思想有异曲同工之妙呢
 * 这里我们要注意的是 分开后的是 list而不是一个数, 所以我们要对他进行排序
 * 时间复杂度 : O(nlogn)
 * 空间复杂度 : O(n)
 *
 * 2. 假如不去两个两个的合并, 而是所有的链表一起合并, 只不过是一个一个的节点取出
 * 上面我们说了排序的方式, 说到了堆, 如果我们将链表的所有节点全都放在一个小根堆里
 * 面, 然后再将这些节点一个一个取出, 组成一个新的链表, 也是行的通的
 * 注意将值塞进小根堆的时候要小心, 因为可能在读数据的时候读成环, 正确的做大应该是
 * 先只赛每一个 list的头结点, 等这个头结点存进新链表中后再将后面的节点塞入queue
 */

public class Main {

//    public static void main(String[] args) {
//        Main test = new Main();
//        // 创建第一个链表：-2 -> -1 -> -1 -> -1
//        ListNode list1 = new ListNode(-2);
//        list1.next = new ListNode(-1);
//        list1.next.next = new ListNode(-1);
//        list1.next.next.next = new ListNode(-1);
//
//        // 创建第二个链表：空链表
//        ListNode list2 = null;
//
//        // 构造 lists 数组
//        ListNode[] lists = new ListNode[]{list1, list2};
//
//        test.mergeKLists(lists);
//    }

    // ************************************************
    // 1. 两个两个链表的排序 (基于归并排序)
    public ListNode mergeKLists1(ListNode[] lists) {
        return merge(lists, 0, lists.length - 1);
    }


    // 将链表分成一个一个单独的链表
    private ListNode merge (ListNode[] lists, int left, int right) {

        // 我们需要特殊判断一下这个条件, 因为该我们的 lists有可能是空的, 这个时候 right > left
        // 在继续向下进行就会数组就会越界
        if (left > right) {
            return null;
        }

        // 当分成一个一个单独的链表时, 我们就不需要再分了, 直接返回这个链表
        if (left == right) {
            return lists[left];
        }

        // 中分大法
        int mid = (left + right) / 2;

        // 分开取到两个单独的 list
        // 这里也是与正常归并不同的地方, 这里我们需要得到分开的这两个链表
        // 然后对他们进行排序
        // 正常的直就得到下标了, 然后就可以基于数组排序了
        ListNode list1 = merge(lists, left, mid);
        ListNode list2 = merge(lists, mid + 1, right);

        // 排序链表
        // 这也是不同点, 正常的是依照下标排序数组了
        return mergeSort(list1, list2);
    }

    // 这里排序两个链表和 21.合并两个有序链表一样
    private ListNode mergeSort(ListNode list1, ListNode list2) {
        if (list1 == null) {
            return list2;
        }
        if (list2 == null) {
            return list1;
        }
        if (list1.val <= list2.val) {
            list1.next = mergeSort(list1.next, list2);
            return list1;
        } else {
            list2.next = mergeSort(list1, list2.next);
            return list2;
        }
    }

    // ********************************************************
    // 2. 全部一起排序 (基于小根堆来排序)
    public ListNode mergeKLists(ListNode[] lists) {


        // 创建小根堆 (优先级队列)
        // 注意创建方式
        // a - b : 小
        // b - a : 大

        // 创建虚拟节点
        ListNode newHead = new ListNode(0);

        // 打工节点, 负责将节点给连接起来
        ListNode prev = newHead;

        // 创建小根堆
        PriorityQueue<ListNode> queue = new PriorityQueue<>((a, b) -> a.val - b.val);

        // 将每个链表的首节点加入堆中
        for (ListNode node : lists) {
            if (node != null) {
                queue.offer(node);
            }
        }

        // 读取最小的节点, 连接到新链表上, 并将他后面的节点加入堆中
        while (!queue.isEmpty()) {
            ListNode cur = queue.poll();
            prev.next = cur;
            prev = cur;
            if (cur.next != null) {
                queue.offer(cur.next);
            }
        }

        // 返回结果
        return newHead.next;
    }

}

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
